// import { listNodeToList } from '../../helper/ListNode'

function Node(val = -1, next = null, prev = null) {
  this.val = val
  this.next = next
  this.prev = prev
}

export var MyLinkedList = function () {
  this.head = new Node(-1)
  this.tail = new Node(-1)
  this.head.next = this.tail
  this.tail.prev = this.head
  this.size = 0
}

MyLinkedList.prototype.getNode = function (index) {
  if (index > this.size - 1) return null
  if (index > this.size >> 1) {
    let cur = this.tail.prev
    let i = this.size - 1
    while (cur !== this.head) {
      if (i === index) {
        return cur
      }
      i--
      cur = cur.prev
    }
  } else {
    let cur = this.head.next
    let i = 0
    while (cur !== this.tail) {
      if (i === index) {
        return cur
      }
      i++
      cur = cur.next
    }
  }
}

MyLinkedList.prototype.addNode = function (node, next) {
  const prev = next.prev
  node.prev = prev
  node.next = next
  prev.next = node
  next.prev = node
}

/**
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.get = function (index) {
  const node = this.getNode(index)
  return node ? node.val : -1
}

/**
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function (val) {
  this.size++
  const node = new Node(val)
  const next = this.head.next
  this.addNode(node, next)
}

/**
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function (val) {
  this.size++
  this.addNode(new Node(val), this.tail)
}

/**
 * @param {number} index
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function (index, val) {
  if (index === this.size) return this.addAtTail(val)
  const node = new Node(val)
  const next = this.getNode(index)
  if (next) {
    this.size++
    this.addNode(node, next)
  }
}

/**
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function (index) {
  const node = this.getNode(index)
  if (node) {
    this.size--
    const prev = node.prev
    const next = node.next
    prev.next = next
    next.prev = prev
  }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * var obj = new MyLinkedList()
 * var param_1 = obj.get(index)
 * obj.addAtHead(val)
 * obj.addAtTail(val)
 * obj.addAtIndex(index,val)
 * obj.deleteAtIndex(index)
 */
